package org.example.algorithm.dp;

//输入：word1 = "horse", word2 = "ros"
//输出：3
public class MinDistanceSolution {

    public static void main(String[] args) {
        MinDistanceSolution solution = new MinDistanceSolution();
        int ans = solution.minDistance("intention", "execution");
        System.out.println(ans);
    }

    //dp方式
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if (len1 == len2 && len1 == 0) {
            return 0;
        }
        int[][] dp = new int[len1+1][len2+1];
        for (int i=0;i<=len1;i++) {
            dp[i][0] = i;
        }
        for (int j=0;j<=len2;j++) {
            dp[0][j] = j;
        }
        for (int i=0;i<len1;i++) {
            for (int j=0;j<len2;j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i+1][j+1] = dp[i][j];
                } else {
                    dp[i+1][j+1] = Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }

    //回溯法+保存计算结果
    public int minDistance2(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] mem = new int[len1+1][len2+1];
        return dfs(word1, len1, word2, len2, mem);
    }

    private int dfs(String word1, int len1, String word2, int len2, int[][] mem) {
        if (len1 == len2 && len1 == 0) {
            return 0;
        }
        if (mem[len1][len2] > 0) {
            return mem[len1][len2];
        }
        int ans = 0;
        if (len1 == 0 || len2 == 0) {
            ans = len1 == 0 ? len2 : len1;
            mem[len1][len2] = ans;
            return ans;
        }
        if (word1.charAt(len1-1) == word2.charAt(len2-1)) {
            ans = dfs(word1, len1-1, word2, len2-1, mem);
            mem[len1][len2] = ans;
            return ans;
        }
        ans =  Math.min(Math.min(dfs(word1, len1-1, word2, len2-1, mem)
                , dfs(word1, len1, word2, len2-1, mem))
        , dfs(word1, len1-1, word2, len2, mem)) + 1;
        mem[len1][len2] = ans;
        return ans;
    }
}
